//
//  main.cpp
//  dynamic_question
//
//  Created by 胡鑫 on 2017/6/7.
//  Copyright © 2017年 胡鑫. All rights reserved.
//

#include <iostream>
#include <utility>
#include <array>
#include <algorithm>

using namespace std;
typedef pair<int, int> IntPair;
typedef array<IntPair, 5> TypeInfo;


int main(int argc, const char * argv[]) {
    // insert code here...
    std::cout << "Hello, World!\n";
    
    TypeInfo arr_info = {
                            //   GOLD People
        std::make_pair<int, int>(500, 400),
        std::make_pair<int, int>(200, 100),
        std::make_pair<int, int>(300, 400),
        std::make_pair<int, int>(350, 350),
        std::make_pair<int, int>(400, 500)
    };

    const int all_people = 1000;
    
    for(auto iter : arr_info){
        printf("frist: %d, second: %d\n", iter.first, iter.second);
    }
    
    int size = arr_info.size();
    TypeInfo result_set;
    
    int last_index = 0;
    IntPair temp_value = {0, 0};
    for (int i = 0; i < size; ++i) {
        bool bSW = true;
        auto &element = arr_info[i];
        for (int j = 0; j < i; ++j) { //代码块中
            if( temp_value.second + element.second <= all_people )
                break; //直接添加
            
            auto &temp_element = result_set[j];
            
            if( temp_value.second - temp_element.second + element.second <= all_people ){
                if(temp_element.first < element.first){
                    temp_value.first = temp_value.first - temp_element.first + element.first;
                    temp_value.second = temp_value.second -temp_element.second + element.second;
                    result_set[j] = element;
                    bSW = false; //当前循环为替换操作
                }
            }
        }
        if(bSW){
            int temp_people = temp_value.second + element.second;
            if( temp_people <= all_people){
                result_set[last_index++] = element;
                temp_value.first += element.first;
                temp_value.second += element.second;
            }
        }
    }
    
    int nSumGold = 0, nSumPeople = 0;
    for (int i = 0; i < size; ++i) {
        nSumGold += result_set[i].first;
        nSumPeople += result_set[i].second;
        printf("Gold: %d, People: %d\n", result_set[i].first, result_set[i].second);
    }

    
    printf("SumGold: %d, SumPeople: %d\n", nSumGold, nSumPeople);
    return 0;
}
